package cs271.examples.sorting;

/**
 * From 'Data Structures and Algorithms Analysis in Java'
 * by Mark Allen Weiss
 * 
 * see http://www.cs.fiu.edu/~weiss/dsaajava2/code/Sort.java
 */
public class MergeSort {

	public static void mergeSort(int[] a) {
		int[] tmpArray = new int[a.length];
		mergeSort(a, tmpArray, 0, a.length-1);
	}

	private static void mergeSort(int[] a, int[] tmpArray, int left, int right ) {
		if(left < right) {
			int center = (left + right) / 2;
			mergeSort(a, tmpArray, left, center);
			mergeSort(a, tmpArray, center + 1, right);
			merge(a, tmpArray, left, center + 1, right);
		}
	}

	private static void merge(int[] a, int[] tmpArray, int leftPos, int rightPos, int rightEnd) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		// Main loop
		while(leftPos <= leftEnd && rightPos <= rightEnd) {
			if( a[leftPos] <( a[rightPos])) {
				tmpArray[ tmpPos++ ] = a[ leftPos++ ];
			} else {
				tmpArray[ tmpPos++ ] = a[ rightPos++ ];
			}
		}

		while(leftPos <= leftEnd) {    // Copy rest of first half
			tmpArray[ tmpPos++ ] = a[ leftPos++ ];
		}
			

		while(rightPos <= rightEnd ) {  // Copy rest of right half
			tmpArray[ tmpPos++ ] = a[ rightPos++ ];
		}

		// Copy tmpArray back
		for(int i = 0; i<numElements; i++, rightEnd--) {
			a[ rightEnd ] = tmpArray[ rightEnd ];
		}
	}


	public static void printArray(int[] a) {
		for(int i: a) {
			System.out.print(i + ", ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] unsorted = new int[]{6, 4, 5, 0};
		int[] a = new int[]{1, 3};
		int[] b = new int[]{2, 4};
		//printArray(merge(b, a));
		mergeSort(unsorted);
		printArray(unsorted);
	}
}
